package io.github.consoles.dsa;

/**
 * Created by yiihua-013 on 17/6/11.
 */
public class ListGeneralizedQueue<Item> {

    private int  size;
    private Node head;
    private Node tail;

    private class Node {
        Item data;
        Node next;
        Node prev;

        Node(Item item) {
            this.data = item;
        }
    }

    boolean isEmpty() {
        return size == 0;
    }

    void insert(Item item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    Item delete(int k) {
        if (isEmpty() || k < 1 || k > size) throw new ArrayIndexOutOfBoundsException("越界");

        int count = 1;

        Node current = head;
        while (current != null) {
            if (count == k) {
                size--;
                break;
            }
            current = current.next;
            count++;
        }

        if (current == head) {
            current.next.prev = null;
            head = current.next;
            current.next = null;
        } else if (current == tail){
            current.prev.next = null;
            tail = current.prev;
            current.prev = null;
        } else {
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }

        return current.data;
    }
}
